package q662_widthOfBinaryTree;

import CommonClass.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Solution_2 {
    Map<Integer, Integer> levelMin = new HashMap<Integer, Integer>();

    /*
    dfs的方式
    通过记录每一层对应一个开始的idx，然后用当前的idx减去其当层开始的idx就可以得到宽度
     */
    public int widthOfBinaryTree(TreeNode root) {
        return dfs(root, 1, 1);
    }

    public int dfs(TreeNode node, int depth, int index) {
        if (node == null) {
            return 0;
        }
        levelMin.putIfAbsent(depth, index); // 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
        return Math.max(index - levelMin.get(depth) + 1, Math.max(dfs(node.left, depth + 1, index * 2), dfs(node.right, depth + 1, index * 2 + 1)));
    }
}

